public class MyLinkedList {
    static class ListNode {
        public int val;//该节点存储的值
        public ListNode prev;//上一个节点的地址
        public ListNode next;//下一个节点的地址

        public ListNode(int val) {
            this.val = val;//val构造方法
        }
    }
    public ListNode head;//头
    public ListNode last;//尾巴，最后一个节点的地址

    //得到链表的长度
    //方法名称采用小驼峰
    public int size() {
        int len = 0;
        ListNode cur = head;
        //1.判断链表是否为空，链表为空，则直接返回len，len的初始值为0
        if(head == null) {
            return len;
        }
        //遍历链表通过len记数
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        return len;
    }
    //打印链表
    public void display() {
        //1.判断链表是否为空
        if(head == null){
            return;//该方法没有返回值，我们是通过return来结束方法
        }
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        //1.判断链表是否为空
        if(head == null) {
            return true;
        }
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                return false;
            }
            cur = cur.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //1.当链表开始为空时
        if(head == null) {
             head = node;
             last = node;
             return;
        }
        node.next = head;
        head.prev = node;
        head = node;
    }
    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        //1.当链表开始为空时
        if(head == null) {
            head = node;
            last = node;
            return;
        }
        last.next = node;
        node.prev = last;
        last = node;

    }

    // 任意位置插入，第一个数据节点为0下标
    public void  addIndex(int index,int data) {
        int size = size();
        if(index < 0 || index > size) {
            throw new IndexOutOfBounds("双向链表Index不合法");
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size) {
            addLast(data);
            return;
        }
        ListNode cur = head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        ListNode node = new ListNode(data);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
    }

    //删除第一次出现关键字key的节点
    public void remove(int key) {
        ListNode cur = head;

        while(cur != null) {
            if(cur.val == key) {
                //开始删

                if(cur == head) {
                    //删除的是头结点
                    head = head.next;
                    //已经删除了头结点了
                    if(head != null) {
                        //如果我们不是单个节点的链表我们就将头节点的prev置空
                        head.prev = null;
                    }else {
                        last = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        //此时这个地方删除的不是尾节点
                        //cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }else{
                        //也就是当cur.next == null 的时候就是删除的尾节点
                       // cur.prev.next = cur.next;
                       // cur.prev.next = null;   与上一行代码是等价的
                        last = last.prev;
                    }


                }



                return;
            }else {
                cur = cur.next;
            }
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = head;

        while(cur != null) {
            if(cur.val == key) {
                //开始删

                if(cur == head) {
                    //删除的是头结点
                    head = head.next;
                    //已经删除了头结点了
                    if(head != null) {
                        //如果我们不是单个节点的链表我们就将头节点的prev置空
                        head.prev = null;
                    }else {
                        last = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        //此时这个地方删除的不是尾节点
                        //cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }else{
                        //也就是当cur.next == null 的时候就是删除的尾节点
                        // cur.prev.next = cur.next;
                        // cur.prev.next = null;   与上一行代码是等价的
                        last = last.prev;
                    }
                }
                //cur = cur.next;
            }
        /*else {
            cur = cur.next;
        }*/
            cur = cur.next;
        }
    }
    //清空链表

    public void clear() {
        //判断该链表是否本身就为空
        if(head == null) {
            return;
        }
        //链表不为空开始清除
        ListNode cur = head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            //cur.val = null;//这是当val为引用类型时
            cur.prev = null;
            cur = curNext;
        }
        //最后还需要将head和last进行置空
        head = null;
        last = null;

    }

}
